A microfiche appendix has been submitted with this application. The microfiche appendix contains 1077 pages on 17 microfiche. A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner reserves all copyrights in this material.
The invention relates to steganography, and in particular, to methods in which messages are embedded in host signals to create a composite signal in which the message is substantially imperceptible.
Hiding data in imagery or audio is a technique well known to artisans in the field, and is termed xe2x80x9csteganography.xe2x80x9d There are a number of diverse approaches to, and applications of, steganography. A brief survey follows:
British patent publication 2,196,167 to Thorn EMI discloses a system in which an audio recording is electronically mixed with a marking signal indicative of the owner of the recording, where the combination is perceptually identical to the original. U.S. Pat. Nos. 4,963,998 and 5,079,648 disclose variants of this system.
U.S. Pat. No. 5,319,735 to Bolt, Berenak and Newman rests on the same principles as the earlier Thorn EMI publication, but additionally addresses psycho-acoustic masking issues.
U.S. Pat. Nos. 4,425,642; 4,425,661; 5,404,377 and 5,473,631 to Moses disclose various systems for imperceptibly embedding data into audio signalsxe2x80x94the latter two patents particularly focusing on neural network implementations and perceptual coding details.
U.S. Pat. No. 4,943,973 to ATandT discloses a system employing spread spectrum techniques for adding a low level noise signal to other data to convey auxiliary data therewith. The patent is particularly illustrated in the context of transmitting network control signals along with digitized voice signals.
U.S. Pat. No. 5,161,210 to U.S. Philips discloses a system in which additional low-level quantization levels are defined on an audio signal to convey, e.g., a copy inhibit code, therewith.
U.S. Pat. No. 4,972,471 to Gross discloses a system intended to assist in the automated monitoring of audio (e.g. radio) signals for copyrighted materials by reference to identification signals subliminally embedded therein.
U.S. Pat. No. 5,243,423 to DeJean discloses a video steganography system which encodes digital data (e.g. program syndication verification, copyright marking, media research, closed captioning, or like data) onto randomly selected video lines. DeJean relies on television sync pulses to trigger a stored pseudo random sequence which is XORed with the digital data and combined with the video.
European application EP 581,317 discloses a system for redundantly marking images with multi-bit identification codes. Each xe2x80x9c1xe2x80x9d (xe2x80x9c0xe2x80x9d) bit of the code is manifested as a slight increase (decrease) in pixel values around a plurality of spaced apart xe2x80x9csignature points.xe2x80x9d Decoding proceeds by computing a difference between a suspect image and the original, unencoded image, and checking for pixel perturbations around the signature points.
PCT application WO 95/14289 describes the present applicant""s prior work in this field.
Komatsu et al., describe an image marking technique in their paper xe2x80x9cA Proposal on Digital Watermark in Document Image Communication and Its Application to Realizing a Signature,xe2x80x9d Electronics and Communications in Japan, Part 1, Vol. 73, No. 5, 1990, pp. 22-23. The work is somewhat difficult to follow but apparently results simple yes/no determination of whether the watermark is present in a suspect image (e.g. a 1 bit encoded message).
There is a large body of work regarding the embedding of digital information into video signals. Many perform the embedding in the non-visual portion of the signal such as in the vertical and horizontal blanking intervals, but others embed the information xe2x80x9cin-bandxe2x80x9d (i.e. in the visible video signal itself). Examples include U.S. Pat. Nos. 4,528,588; 4,595,950, and 5,319,453; European application 441,702; and Matsui et. al, xe2x80x9cVideo-Steganography: How to Secretly Embed a Signature in a Picture,xe2x80x9d IMA Intellectual Propeerty Project Proceedings, January 1994, Vol. 1, Issue 1, pp. 187-205.
There are various consortium research efforts underway in Europe on copyright marking of video and multimedia. A survey of techniques is found in xe2x80x9cAccess Control and Copyright Protection for Images (ACCOPI), WorkPackage 8: Watermarking,xe2x80x9d Jun. 30, 1995, 46 pages. A new project, termed TALISMAN, appears to extend certain of the ACCOPI work. Zhao and Koch, researchers active in these projects, provide a Web-based electronic media marking service known as Syscop.
Aura reviews many issues of steganography in his paper xe2x80x9cInvisible Communication,xe2x80x9d Helskinki University of Technology, Digital Systems Laboratory, Nov. 5, 1995.
Sandford II, et al. review the operation of their May, 1994, image steganography program (BMPEMBED) in xe2x80x9cThe Data Embedding Method,xe2x80x9d SPIE Vol. 2615, Oct. 23, 1995, pp. 226-259.
A British company, Highwater FBI, Ltd., has introduced a software product which is said to imperceptibly embed identifying information into photographs and other graphical images. This technology is the subject of European patent applications 9400971.9 (filed Jan. 19, 1994), 9504221.2 (filed Mar. 2, 1995), and 9513790.7 (filed Jul. 3, 1995), the first of which has been laid open as PCT publication WO 95/20291.
Walter Bender at M.I.T. has done a variety of work in the field, as illustrated by his paper xe2x80x9cTechniques for Data Hiding,xe2x80x9d Massachusetts Institute of Technology, Media Laboratory, January 1995.
Dice, Inc. of Palo Alto has developed an audio marking technology marketed under the name Argent. While a U.S. Patent Application is understood to be pending, it has not yet been issued.
Tirkel et al, at Monash University, have published a variety of papers on xe2x80x9celectronic watermarkingxe2x80x9d including, e.g., xe2x80x9cElectronic Water Mark,xe2x80x9d DICTA-93, Macquarie University, Sydney, Australia, December, 1993, pp. 666-673, and xe2x80x9cA Digital Watermark,xe2x80x9d IEEE International Conference on Image Processing, Nov. 13-16, 1994, pp. 86-90.
Cox et al, of the NEC Technical Research Institute, discuss various data embedding techniques in their published NEC technical report entitled xe2x80x9cSecure Spread Spectrum Watermarking for Multimedia,xe2x80x9d December, 1995.
Mxc3x6ller et al. discuss an experimental system for imperceptibly embedding auxiliary data on an ISDN circuit in xe2x80x9cRechnergestutzte Steganographie: Wie sie Funktioniert und warum folglich jede Reglementierung von Verschlusselung unsinnig ist,xe2x80x9d DuD, Datenschutz und Datensicherung, 18/6 (1994) 318-326. The system randomly picks ISDN signal samples to modify, and suspends the auxiliary data transmission for signal samples which fall below a threshold.
There are a variety of shareware programs available on the internet (e.g. xe2x80x9cStegoxe2x80x9d and xe2x80x9cWhite Noise Stormxe2x80x9d) which generally operate by swapping bits from a to-be-concealed message stream into the least significant bits of an image or audio signal. White Noise Storm effects a randomization of the data to enhance its concealment.
The invention provides methods for decoding messages from composite signals formed by embedding a message into a host signal. These messages are encoded such that they are substantially imperceptible in the composite signal. The invention applies to a variety of different types of signals, including images, audio and video.
One aspect of the invention is a method of decoding a message embedded into a code signal, which is embedded into a host signal. Together, the code and host signals form a composite signal. The message is comprised of one or more symbols, each being associated with a predetermined signal characteristic. Before message decoding commences, the composite signal may be modified, either by unintentional or intentional manipulation such as compression, filtering, transmission, analog to digital and digital to analog conversion, etc. As such, the decoding process operates on a potentially modified version of the composite signal. To read the message, the decoding process correlates predetermined signal characteristics with the potentially modified composite signal to decode message symbols.
Another aspect of the invention is a method of decoding a message steganographically embedded into a host signal. Prior to message decoding, a message is embedded into the host signal to form a composite signal in which the message is substantially imperceptible. The message embedder adjusts the host signal to encode a signal characteristic associated with message symbol. The decoding process analyzes a potentially modified version of the composite signal to gather evidence of the characteristic associated with the message symbol. Based on the evidence, it determines whether the message symbol is present in the potentially modified version of the composite signal. In contrast to the embodiment described previously, this embodiment does not necessarily require the use of correlation to decode a message.
Yet another aspect of the invention is a method of decoding a message that uses one or more known message symbols to check the validity of a message extracted from a potentially modified version of a composite signal. The method analyzes the composite signal to gather evidence of characteristics associated with the message symbols in the message. Based on the evidence, it estimates message symbols. It compares the estimated message symbols with one or more message symbols known to be included in the message to assess whether the composite signal has a valid message.
Further features of the invention will become apparent with reference to the following detailed description and accompanying drawings.